package basic.study.algorithms.struct;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Kevin
 * @date 2020/2/14 13:29
 */
public class Graph {//无向图
    private int v;//定点个数
    private LinkedList<Integer> adj[];//邻接表

    public Graph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];
        for(int i=0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {//无向图一边存两次
        adj[s].add(t);
        adj[t].add(s);
    }

    public void bfs(int s, int t) {
        if(s == t) return ;
        boolean[] visited = new boolean[v];
        //用来存储已被访问的节点
        visited[s] = true;
        //用来存储已经被访问、但相连的顶点还没有被访问的顶点
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        //用来记录搜索路径，是反向的不过
        int[] prev = new int[v];
        while(!queue.isEmpty()) {
            int w = queue.poll();
            for(int i = 0; i < adj[w].size(); i++) {
                int q = adj[w].get(i);
                if(!visited[q]) {
                    prev[q] = w;
                    if(q == t) {
                        print(prev, s, t);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    boolean found = false;// 全局变量或者类成员变量
    public void dfs(int s, int t) {
        found = false;
        boolean[] visited = new boolean[v];
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        recurDfs(s, t, visited, prev);
        print(prev, s, t);
    }
    private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
        if (found == true) return;
        visited[w] = true;
        if (w == t) {
            found = true;
            return;
        }
        for (int i = 0; i < adj[w].size(); i++) {
            int q = adj[w].get(i);
            if (!visited[q]) {
                prev[q] = w;
                recurDfs(q, t, visited, prev);
            }
        }
    }

    public void print(int[] prev, int s, int t) {
        if(prev[t] != -1 && t != s){
            print(prev, s, prev[t]);
        }
        System.out.println(t + " ");
    }
}
